package com;

import java.util.concurrent.atomic.AtomicReference;

public class  MyStack<T> {
    private final AtomicReference<Element<T>> head = new AtomicReference<Element<T>>(null);

    public void push(T value){
    	Element<T> newElement = new Element<T>(value);

        while(true){
        	Element<T> oldHead = head.get();
            newElement.next = oldHead;

            //Trying to set the new element as the head
            if(head.compareAndSet(oldHead, newElement)){
                return;
            }
        }
    }

    public T pop(){
        while(true){
            Element<T> oldHead = head.get();

            //The stack is empty
            if(oldHead == null){
                return null;
            }

            Element<T> newHead = oldHead.next;

            //Trying to set the new element as the head
            if(head.compareAndSet(oldHead, newHead)){
                return oldHead.t;
            }
        }
    }
    
    

    private static final class Element<T> {
        private final T t;
        private Element<T> next;

        private Element(T t) {
            this.t = t;
        }
    }
}